{UTF-8}
Unit List;
Interface
Uses ListNode;
Type
	{функции подаются два аргумента, указателя на данные,
	хранящиеся в списке}
	{она должна их сравниватьb возвращать true, если она равны,
	или false, если они различны}
	comparator = function(const arg1:pointer; const arg2:pointer):boolean;
	ListIterator = pointer;
	PList = ^Tlist;
	TList = object
	Private
		size:			t_size;
		first:			pointer;
		last:			pointer;
		numberElement:	t_size;
		maxNumberElement:longint;
	Public
		Constructor	init(s:t_size);
		Destructor	done;
		{метод помещает arg в конец списка}
		Procedure	push_back(var arg);
		{метод помещает arg в начало списка}
		Procedure	push_front(var arg);
		{метод удаляет элемент из конца списка}
		Procedure	pop_back;
		{метод удаляет элемент из начала списка}
		Procedure	pop_front;
		{метод возвращает true и первый элемент списка в arg, или false}
		Function	front(var arg):boolean;
		{метод возвращает true и последний элемент списка в arg, или false}
		Function	back(var arg):boolean;
		{метод проверяет список на пустоту}
		Function	empty:boolean;
		{метод возвращает количество элементо в списке}
		Function	get_size:t_size;
		{метод возвращает максимально возможное количество
		элементов в списке}
		Function	max_size:longint;
		{метод возвращает указатель на элемент списка, содержимое
		которого совпадает с arg}
		Function	find(var arg):ListIterator;
		{arg: указатель на данные, которые хотим найти в списке}
		{comp: функция, умеющая сравнивать данные, хранящиеся внутри списка}
		Function	find_by_comparator(const arg:pointer; comp:comparator):ListIterator;
		{метод удаляет элемент, на который указывает it}
		Procedure	remove(const it:ListIterator);
		{элемент arg вставляется перед элементом, на которой указывает it}
		Procedure	insert(const it:ListIterator; var arg);
		{метод возвращает true и it-ый элемент списка, или false}
		Function	get(const it:ListIterator; var arg):boolean;
		{метод возвращает следующий элемент после it элемента}
		Function	get_next(it:ListIterator):ListIterator;
		{метод возвращает предыдущий элемент после it элемента}
		Function	get_prev(it:ListIterator):ListIterator;
		Function	get_first:ListIterator;
		Function	get_last:ListIterator;

		{метод перемещает первый элемент списка в конец}
		Procedure move_front_to_back;
	end;
Implementation

(*
 * * * * *
 * TList *
 * * * * * 
*)

Constructor TList.init;
begin
	size:=s;
	(*размер сегмента - размер списка разделить на 
	(размер элемента списка + размер данных, хранящихся в нём)*)
	maxNumberElement:= (((MemAvail div 8) - ((sizeof(TList) div 8) + (ord((sizeof(TList)mod 8) <> 0 )))) div
						((sizeof(TListNode) div 8) + (ord((sizeof(TListNode)mod 8) <> 0)) + (size div 8) + (ord((size mod 8) <> 0))));
	numberElement:=0;
	first:=nil;
	last:=nil;
end;
Destructor TList.done;
begin
	while first <> nil do
		pop_front;
end;
Procedure TList.push_back;
var
	cur,
	prev:PListNode;
begin
	inc(NumberElement);
	cur:=new(PListNode, init(arg, size));	
	{если список пуст}
	if (first = nil) then
		begin
			first:=cur;
			last:=cur;
		end
	else
		begin
			{если в списке только один элемент}
			prev:=	last;
			prev^.set_next(cur);
			cur^.set_prev(prev);
			last:=cur;
		end;
end;
Procedure TList.push_front;
var
	cur,
	next:PListNode;
begin
	inc(numberElement);
	cur:=new(PListNode, init(arg, size));
	{если список пуст}
	if (first = nil) then
		begin
			first:=cur;
			last:=cur;
		end
	else
		begin
			next:=first;
			next^.set_prev(cur);
			cur^.set_next(next);
			first:=cur;
		end;
end;
Procedure TList.pop_back;
var
	cur:PListNode;
begin
	{если список пуст, выходим}
	if (last = nil) then
		exit;
	
	dec(numberElement);
	cur:=last;
	last:=cur^.get_prev;
	{если список стал пустым, запишем в first nil}
	if (last = nil) then 
		first:=nil
	else
		{иначе установим у нового последнего элемента указатель
		на следующий как nil}
		cur^.get_prev^.set_next(nil);
	
	cur^.done;
	if (cur <> nil) then dispose(cur);
end;
Procedure TList.pop_front;
var
	cur:PListNode;
begin
	{если список пуст, выходим}
	if(first = nil) then
		exit;
	dec(numberElement);
	cur:=first;
	first:=cur^.get_next;
	{если список стал пустым, запишем last nil}		
	if (first = nil) then 
		last:=nil
	else
		cur^.get_next^.set_prev(nil);
	cur^.done;
	if (cur <> nil) then dispose(cur);
end;
Function TList.front;
var
	cur:PListNode;
begin
	if (empty) then
		begin
			front:=false;
			exit;
		end
	else
		begin
			front:=true;
			cur:=first;
			cur^.get_data(arg);
		end;
end;
Function TList.back;
var
	cur:PListNode;
begin
	if (empty) then
		begin
			back:=false;
			exit;
		end
	else
		begin
			back:=true;
			cur:=last;
			cur^.get_data(arg);
		end;
end;
Function TList.empty;
begin
	if (first = nil) and (last = nil) then empty:=true
	else empty:= false;
end;
Function TList.get_size;
begin
	get_size:=numberElement;
end;
Function TList.max_size;
begin
	max_size:=maxNumberElement;
end;
Function TList.find;
var
	cur:PListNode;
begin
	cur:=first;
	while(cur <> nil) do
		begin
			if (cur^.equal(arg)) then break;
			cur:=cur^.get_next;
		end;
	find:=cur;
end;
Function TList.find_by_comparator;
var
	cur:PListNode;
begin
	cur:=first;
	while(cur <> nil) do
		begin
			if (comp(arg,cur^.get_data_ptr)) then break;
			cur:=cur^.get_next;
		end;
	find_by_comparator:=cur;
end;
Procedure TList.remove;
var
	cur,
	prev,
	next:PListNode;
begin
	{если был передан nil, выходим из метода}
	if (it = nil) then exit;
	cur:=first;
	(*в цикле ищем элемент, который нужно удалить*)
	while (cur <> nil) do
		begin
			if (cur = it) then  break;
			cur:=cur^.get_next;
		end;
	{если такого элемента в списке нет, выходим}
	if (cur = nil) then exit;
	{если удалить нужно первый элемент, вызываем pop_front}
	if (cur = first) then
		begin
			pop_front;
			exit;
		end;
	{если удалить нужно последний элемент, вызываем pop_back}
	if (cur = last) then
		begin
			pop_back;
			exit;
		end;
	{стандартное удаление элемента, у которого есть следующий
	и предыдущий}
	dec(numberElement);
	prev:=cur^.get_prev;
	next:=cur^.get_next;
	{перебрасываем указатели через удаляемый элемент}
	prev^.set_next(next);
	next^.set_prev(prev);
	{удаляем теущий элемент}
	cur^.done;
	if (cur <> nil) then dispose(cur);
end;
Procedure TList.insert;
var
	cur,
	prev,
	element:PListNode;
begin
	{если был передан nil, выходим из метода}
	if (it = nil) then exit;
	cur:=first;
	{ищем элемент it}
	while (cur <> nil) do
		begin
			if (cur = it) then break;
			cur:=cur^.get_next;
		end;
	{если такого элемента нет в списке выходим}
	if (cur = nil) then exit;
	{иначе такой элемент найдет}
	{если он равен первому, то вызываем push_front}
	if (cur = first) then
		begin
			push_front(arg);
		end
	else
		begin
			{стандартная вставка нового элемента}
			inc(numberElement);		
			prev:=cur^.get_prev;
			element:=new(PListNode, init(arg, size));
			element^.set_next(cur);
			element^.set_prev(prev);
			cur^.set_prev(element);
			prev^.set_next(element);
		end;
end;
Function TList.get;
var
	cur:PListNode;
begin
	{если в метод был передан nil, выходим из функции}
	if (it = nil) then
		begin
			get:=false;
			exit;
		end;
	cur:=first;
	{ищем элемент, на который указывает it}
	while (cur <> nil) do
		begin
			if (cur = it) then break;
			cur:=cur^.get_next;
		end;
	{если не нашли, то выходим из функции}
	if (cur = nil) then
		begin
			get:=false;
			exit;
		end;
	{возвращаем элемент}
	cur^.get_data(arg);
	get:=true;
end;
Procedure TList.move_front_to_back;
var
        cur:PListNode;
begin
		(*если в очереди только один или ни одного элемента, выходим*)
		if (first = last) then exit;
		cur:=last;
		cur^.set_next(first);
		cur:=first;
		cur^.set_prev(last);
		last:=first;
		first:=cur^.get_next;
		cur^.set_next(nil);
		cur:=first;
		cur^.set_prev(nil);
end;
Function TList.get_next;
var
	cur:PListNode;
begin
	cur:=it;
	get_next:=cur^.get_next;
end;
Function TList.get_prev;
var
	cur:PListNode;
begin
	cur:=it;
	get_prev:=cur^.get_prev;
end;
Function TList.get_first;
begin
	get_first:=first;
end;
Function TList.get_last;
begin
	get_last:=last;
end;
end.